package main

//#link: https://leetcode-cn.com/problems/throne-inheritance/
func main() {

}

type Node struct {
	name      string
	next      *Node
	last      *Node
	isDeleted bool
}

var (
	tempMap = make(map[string]*Node)
	head    = &Node{name: "king"}
	tail    = &Node{name: ""}
)

type ThroneInheritance struct {
	*Node
}

func Constructor(kingName string) ThroneInheritance {
	root := new(Node)
	root.name = kingName
	root.next = tail
	head.next = root
	tempMap[kingName] = root
	return ThroneInheritance{
		root,
	}
}
func (this *ThroneInheritance) Birth(parentName string, childName string) {
	node := &Node{name: childName}
	tempMap[childName] = node
	p := tempMap[parentName]
	tmp := p
	for tmp.last != nil {
		tmp = tmp.last
	}
	node.next = tmp.next
	tmp.next = node
	p.last = node
}

func (this *ThroneInheritance) Death(name string) {
	node := tempMap[name]
	node.isDeleted = true
}

func (this *ThroneInheritance) GetInheritanceOrder() []string {
	ans := make([]string, 0)
	tmp := head
	for tmp.next != nil {
		if !tmp.isDeleted {
			ans = append(ans, tmp.name)
		}
		tmp = tmp.next
	}
	return ans
}

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * obj := Constructor(kingName);
 * obj.Birth(parentName,childName);
 * obj.Death(name);
 * param_3 := obj.GetInheritanceOrder();
 */
